﻿#pragma once
//公共头文件
#include<iostream>
#include<thread>
#include<vector>
#include<unordered_map>
#include<algorithm>

#include<time.h>
#include<assert.h>

#include<mutex>
using std::cout;
using std::endl;

static const size_t MAX_BYTES = 256 * 1024;	//ThreadCache最大单个内存块大小
static const size_t NFREELIST = 208;		//ThreadCache CentralCache哈希桶桶数量
static const size_t NPAGES = 129;			//PageCache哈希桶桶数量[1,128]
static const size_t PAGE_SHIFT = 13;		//字节到页的转换，假定一页8kb


//预定义页id
#ifdef _WIN64	//32位配置，有_WIN32定义，没有_WIN64定义
	typedef unsigned long long PAGE_ID;
#elif _WIN32	//64位配置，有_WIN32定义，有_WIN64定义
	typedef size_t PAGE_ID;
#else
	//linux
#endif

#ifdef _WIN32
#include<Windows.h>
#else
// linux下brk mmap等 
#endif

// 直接去堆上按页申请空间 
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32					//假设一页是8K
void* ptr = VirtualAlloc(0, kpage * 8 * 1024, MEM_COMMIT | MEM_RESERVE,
	PAGE_READWRITE);		//位运算kpage>>13
#else
// linux下brk mmap等 
#endif
if (ptr == nullptr)
throw std::bad_alloc();//抛异常
return ptr;
}
// 直接去堆上按页释放空间 
inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// sbrk unmmap等 
#endif
}

//公共的成员函数//包含到多个文件的头文件中会导致“多重定义”错误
				//方法1 改成内联  方法2 .h声明 .cpp实现 方法3 static只在当前文件可见
static void*& NextObj(void* obj)//返回原始内存位置的引用，一个左值
{
	return *(void**)obj;//返回的obj的引用，即obj所指向内存块
						//前4/8字节的别名
}

//管理切分好的小对象的自由链表(即一个桶)
class FreeList
{
public:
	void Push(void* obj)
	{					
		assert(obj);	
		//头插
		//*(void**)obj = _freeList;//相当于对obj解引用，不改变obj的值
		//改变obj所指向内存块的内容，以void*大小访问
		NextObj(obj) = _freeList;
		_freeList = obj;
		_size++;
	}
	//范围插入					//最后一个内存块起始地址
	void PushRange(void* start, void* end,size_t n)
	{
		NextObj(end) = _freeList;
		_freeList = start;

		_size += n;
	}

	void* Pop()
	{
		assert(_freeList);
		//头删
		void* obj = _freeList;
		_freeList = NextObj(obj);
		_size--;
		return obj;
	}

	//范围删除
	void PopRange(void*& start, void*& end, size_t n)
	{
		assert(n <= _size);//

		start = _freeList;
		end = start;
		//end走n-1步
		for (size_t i = 0; i < n - 1; i++)
		{
			end = NextObj(end);
		}
		_freeList = NextObj(end);
		NextObj(end) = nullptr;
		_size -= n;
	}

	bool Empty()
	{
		return _freeList == nullptr;
	}

	size_t& MaxSize()
	{
		return _maxSize;
	}

	size_t Size()
	{
		return _size;
	}
private:
	void* _freeList = nullptr;
	size_t _maxSize = 1;		//帮助从中心缓存获取对象
	size_t _size = 0;			//自由链表大小
};

//计算对象大小的对齐映射规则,不同size对应哈希桶哪个桶
class SizeClass
{
public:
	//类似于tcmalloc的映射规则
	// 整体控制在最多10%左右的内碎⽚浪费 
	// [1,128]				8byte对⻬		freelist[0,16) 
	// [128+1,1024]			16byte对⻬		freelist[16,72) 
	// [1024+1,81024]		128byte对⻬		freelist[72,128) 
	// [8*1024+1,641024]	1024byte对⻬	freelist[128,184) 
	// [64*1024+1,256*1024] 8*1024byte对⻬	freelist[184,208)
	
	////对齐数							//对齐数
	//size_t _RoundUp(size_t size, size_t alignNUm)
	//{
	//	size_t alignSize;
	//	if (size % alignNUm != 0)
	//	{
	//		alignSize = (size / alignNUm + 1) * alignNUm;
	//	}
	//	else
	//	{
	//		alignSize = size;
	//	}
	//	return alignSize;
	//}
	//返回内存对齐到多大
	static inline size_t _RoundUp(size_t size, size_t alignNum)
	{	//移位运算和按位与或效率比较高，算术运算效率较低
		return ((size+ alignNum - 1) & ~(alignNum - 1));
		//1-8  -->8
		//9-16 -->16
		//17-24-->24
	}

	//对齐	返回size对齐到多大
	static inline size_t RoundUp(size_t size)//不需要调用成员变量
	{										//直接用类名调用方便
		if (size <= 128)					//设置成静态
		{
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return _RoundUp(size, 8 * 1024);
		}
		else
		{
			return _RoundUp(size, 1 << PAGE_SHIFT);//以页为单位对齐
		}

	}

	////映射
//size_t _Index(size_t bytes, size_t alignNum)
//{
//	if (bytes % alignNum == 0)
//	{
//		return bytes / alignNum - 1;
//	}
//	else
//	{
//		return bytes / alignNum;
//	}
//}
	//映射	在几号桶							//1左移几位得到alignNum
	static inline size_t _Index(size_t bytes, size_t align_shift)
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
		//1-8  -->0
		//9-16 -->1
		//17-24-->2
	}
	// 计算映射的哪⼀个⾃由链表桶 
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);
		// 每个区间有多少个链 
		static int group_array[4] = { 16, 56, 56, 56 };
		if (bytes <= 128) {
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024) {
			return _Index(bytes - 128, 4) + group_array[0];
		}
		else if (bytes <= 81024) {
			return _Index(bytes - 1024, 7) + group_array[1] + group_array[0];
		}
		else if (bytes <= 64 * 1024) {
			return _Index(bytes - 8 * 1024, 10) + group_array[2] +
				group_array[1] + group_array[0];
		}
		else if (bytes <= 256 * 1024) {
			return _Index(bytes - 64 * 1024, 13) + group_array[3] +
				group_array[2] + group_array[1] + group_array[0];
		}
		else {
			assert(false);
		}
		return -1;
	}

	// ⼀次thread cache从中心缓存获取多少个 
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0);
		if (size == 0)
			return 0;
		// [2, 512]，⼀次批量移动多少个对象的(慢启动)上限值 
		// ⼩对象⼀次批量上限⾼ 
		// ⼩对象⼀次批量上限低 
		int num = MAX_BYTES / size;	//中间正常分配
		if (num < 2)				//下限锁死
			num = 2;
		if (num > 512)				//上限锁死
			num = 512;
		return num;
	}

// 计算⼀次向系统获取⼏个⻚ 
 // 单个对象 8byte 
 // ...
 // 单个对象 256KB 
	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);	//多少个内存块
		size_t npage = num * size;		//多少字节

		npage >>= PAGE_SHIFT;			//跟页的转换

		if (npage == 0)
			npage = 1;

		return npage;
	}
};



//管理多个连续页大块内存跨度结构
struct Span
{
	PAGE_ID _pageid = 0;		//大块内存起始页的页号
	size_t _n = 0;				//页的数量

	Span* _next = nullptr;		//双向链表的结构
	Span* _prev = nullptr;

	size_t _objSize = 0;		//切好的小对象的大小
	size_t _useCount = 0;		//切好小块内存，被分配给thread cache的计数
	void* _freeList = nullptr;	//切好的小块内存的自由链表

	bool _isUse = false;		//是否在被使用，即分给central cache
};
//带头双向循环链表
class SpanList
{
public:
	//这里必须用构造函数完成初始化
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}
	//支持遍历
	Span* Begin()
	{
		return _head->_next;
	}
	Span* End()
	{
		return _head;
	}

	bool Empty()
	{
		return _head->_next == _head;
	}

	//头插
	void PushFront(Span* span)
	{
		Insert(Begin(), span);
	}
	//插入
	void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		assert(newSpan);

		Span* prev = pos->_prev;
		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;
	}

	//头删
	Span* PopFront()
	{
		Span* front = _head->_next;
		Erase(front);
		return front;
	}

	//删除
	void Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head);

		////1.条件断点
		// 2.查看栈帧
		//if (pos == _head)
		//{
		//	int x = 0;
		//}

		Span* prev = pos->_prev;
		Span* next = pos->_next;

		prev->_next = next;
		next->_prev = prev;
		//不用delete pos,删Span是归还给page cache

	}
private:
	Span* _head;
public://改成public,外面才能访问加锁
	std::mutex _mtx;	//桶锁
};
